import java.util.LinkedList;
import java.util.PriorityQueue;


public class AStarBFS 
{
	
	private static class MoveWrap implements Comparable<MoveWrap>
	{
		private Move move;
		private Cord[] goals;
		
		public MoveWrap( Move move, Cord ... goals )
		{
			this.move = move;
			this.goals = goals;
		}

		@Override
		public int compareTo(MoveWrap o) 
		{
			int ref = calculateHeuristicPathLengthBetween(o.move, o.goals[0]);
			for ( int i = 1; i < goals.length; i++)
			{
				ref = Math.min( ref , calculateHeuristicPathLengthBetween(o.move, o.goals[i]) );
			}
			
//			int ref = calculateHeuristicPathLengthBetween(o.move, o.goal);
//			int self = calculateHeuristicPathLengthBetween(move, goal);
			
			int self = calculateHeuristicPathLengthBetween(this.move, this.goals[0]);
			for ( int i = 1; i < goals.length; i++)
			{
				self = Math.min( ref , calculateHeuristicPathLengthBetween(this.move, this.goals[i]) );
			}
			
			if ( self < ref )
			{
				return -1;
			}
			else if ( self > ref )
			{
				return 1;
			}
			else
			{
				return 0;
			}
		}
	}

	public static int calculateHeuristicPathLengthBetween( Cord c1, Cord c2 )
	{
		return (Math.abs( c1.getX()-c2.getX() ) + Math.abs( c1.getY()-c2.getY() ));
	}
	
//	public static MoveRule moveRule = new PlayerMove();
	
	public static int calculatePathLength( Board board, MoveRule moveRule, Cord start, Cord ... goals )
	{
		

//		Move playerBegin = new MoveImpl( start.getX() , start.getY(), null, "");
		Move playerBegin = new MoveImpl( start.getX() , start.getY(), null, 0);
		
//		LinkedList<Move> queue = new LinkedList<Move>();
		PriorityQueue<MoveWrap> queue = new PriorityQueue<MoveWrap>();
		
//		queue.add(playerBegin);
		
		queue.add( new MoveWrap( playerBegin, goals ) );
		
		VisitedCellHelper visited = board.getVisitedBoardHelper();
		
		while( !queue.isEmpty() )
		{

			Move currentMove = queue.remove().move; // BFS
			
//			System.out.println( currentMove.getX() +":"+ currentMove.getY() );
			
			if ( visited.unisitedCell(currentMove) )
			{
				visited.registerCellAsVisited(currentMove);
				
				for ( Cord goal : goals )
				{
					if (( board.getCellType( goal ) != Board.CellType.BoxOnGoal ) &&
					   ( currentMove.equalsCord(goal) ))
//						if ( ( board.getCellType(currentMove) == Board.CellType.GoalSquare ) ||
//								( board.getCellType(currentMove) == Board.CellType.PlayerOnGoalSquare ) )
								{
//									return currentMove.getPathToThis().length();
									return currentMove.getPathLenth();
								}
				}
				

						
						for ( Move m : board.getLegalMoves(currentMove, moveRule) )
						{
//							queue.addLast( m );
							queue.add( new MoveWrap( m, goals ) );
						}
				
			}
			else
			{
				// Do nothing
			}
		
			
		}
		return Integer.MAX_VALUE;

		
	}

}
